package com.xupt.top;

/**
 * @author zhaoxin
 * @title: RemoveNthFromEnd
 * @projectName LeetCode
 * @description: 19. 删除链表的倒数第N个节点
 * @date 2019/12/11 16:21
 */
public class RemoveNthFromEnd {

    /**
     * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
     *
     * 示例：
     *
     * 给定一个链表: 1->2->3->4->5, 和 n = 2.
     *
     * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
     * 说明：
     *
     * 给定的 n 保证是有效的。
     *
     * 进阶：
     *
     * 你能尝试使用一趟扫描实现吗？
     *
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {

        // 链表只有一个元素，直接删除
        if (head.next == null){
            head = null;
            return head;
        }

        ListNode cur = head;
        int size = 1;
        // 查找链表长度
        while (cur.next != null){
            cur = cur.next;
            size++;
        }

        // 删除头节点元素
        if (size == n){
            cur = head.next;
            head.next = null;
            return cur;
        }
        // 定位目标节点的前一个节点
        int preIndexOf = (size - n) - 1;
        cur = head;
        while (preIndexOf != 0){
            cur = cur.next;
            preIndexOf--;
        }
        // 删除指定位置节点
        cur.next = cur.next.next;
        return head;
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(3);
        //ListNode listNode3 = new ListNode(4);
        //ListNode listNode4 = new ListNode(5);
        listNode.next = listNode1;
        listNode1.next = listNode2;
        //listNode2.next = listNode3;
        //listNode3.next = listNode4;
        RemoveNthFromEnd removeNthFromEnd = new RemoveNthFromEnd();
        removeNthFromEnd.removeNthFromEnd(listNode, 3);


    }


}
